Rotting Oranges

Try to solve the Rotting Oranges problem.

Statement#

Consider an m×nm \times n grid containing cells with three potential values:

  • 00, which indicates an unoccupied cell.

  • 11, representing a freshly picked orange.

  • 22, indicating a rotten orange.

Any fresh orange that is 4–directionally adjacent to a rotten orange will also turn rotten with each passing minute.

Your task is to determine the minimum time required for all cells to have rotten oranges. In case, this objective cannot be achieved, return −1-1.

Constraints:

  • m == grid.length

  • n == grid[i].length

  • 11 ≤\leq m, n ≤\leq 1010

  • grid[i][j] is 01, or 2.

Examples#

svg viewer

1 of 11

svg viewer

2 of 11

svg viewer

3 of 11

svg viewer

4 of 11

svg viewer

5 of 11

svg viewer

6 of 11

svg viewer

7 of 11

svg viewer

8 of 11

svg viewer

9 of 11

svg viewer

10 of 11

svg viewer

11 of 11

Understand the problem#

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

Rotting Oranges

3

What is the output if the following (3×3)(3 \times 3) grid is given as input?

[111121111]\begin{bmatrix} 1 & 1 & 1 \\ 1 & 2 & 1 \\ 1 & 1 & 1 \end{bmatrix}

Your Answer
A)

1

Correct Answer
B)

2

Explanation

Starting from the rotten orange at coordinate (1, 1), all of the adjacent cells will get rotten, this would take 1 minute, and then all the remaining corner cells will rot, this would take another minute. So, a total of 2 minutes are required to rot all the oranges.

C)

5

Question 3 of 33 attempted

Try it yourself#

Implement your solution in the following coding playground:

The optimal solution to this problem runs in O(m x n) time and takes O(m x n) space.

Python
usercode > main.py
Powered by AI
Input #1
Rotting Oranges

You might want to go over the Tree Breadth-first Search pattern again.

Asteroid Collision

Add Binary